home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / jpl_c.zip / SORTQ.C < prev    next >
Text File  |  1986-05-18  |  3KB  |  88 lines
  1. /* 1.0  11-12-84 */
  2. /************************************************************************
  3.  *            Robert C. Tausworthe                *
  4.  *            Jet Propulsion Laboratory            *
  5.  *            Pasadena, CA 91009        1984        *
  6.  ************************************************************************
  7.  *    Quicksort subroutine, using the usual C. A. R. Hoare recursive
  8.  *    algorithm, such as described in 
  9.  *
  10.  *    Knuth, D. E., FUNDAMENTAL ALGORITHMS, Vol. III, "Sorting and 
  11.  *    Searching," Addison-Wesley, pp. 116.
  12.  *
  13.  *    It is written so the array type is unknown to the algorithm, but is 
  14.  *    known to comp() and exch().  The comparison function comp(i, j) 
  15.  *    must be positive if, and only if, the array elements indexed by
  16.  *    i and j are out of sort.  The function exch(i, j) must exchange 
  17.  *    array elements indexed by i and j.
  18.  */
  19.  
  20. #include "defs.h"
  21. #include "stdtyp.h"
  22.  
  23. int     (*gcomp)();    /* global compare and exchange functions */
  24. VOID     (*gexch)();
  25.  
  26. /************************************************************************/
  27.     VOID
  28. sortQ(n, comp, exch)        /* Quicksort array of n items compared by
  29.                    comp(i, j), exchanged by exch(i, j)    */
  30. /*----------------------------------------------------------------------*/
  31. unsigned n;
  32. int (*comp)();
  33. VOID (*exch)();
  34. {
  35.     VOID quick();
  36.  
  37.     gcomp = comp;        /* set functions global to this subroutine */
  38.     gexch = exch;
  39.     quick(0, n - 1);    /* quicksort from 0 to n-1 */
  40. }
  41.  
  42. /*\p*********************************************************************/
  43.     LOCAL VOID
  44. quick(low, high)        /* quicksort array from low to high.    */
  45.  
  46. /*----------------------------------------------------------------------*/
  47. unsigned low, high;
  48. {
  49.     unsigned j, partition();
  50.  
  51.     if (low < high)
  52.     {    if ((j = partition(low, high)) IS low)
  53.             quick(low + 1, high);    /* lower segment empty    */
  54.         else if (j IS high)
  55.             quick(low, j-1);    /* upper segment empty    */
  56.         else if (j - low < high - j)
  57.         {    quick(low, j - 1);    /* smaller segment first */
  58.             quick(j + 1, high);    /* minimizes stack depth.*/
  59.         }
  60.         else
  61.         {    quick(j + 1, high);
  62.             quick(low, j - 1);
  63.         }
  64.     }
  65. }
  66.  
  67. /************************************************************************/
  68.     LOCAL unsigned
  69. partition(low, high)    /* partition into lower and upper sets and return
  70.                index of middle (sorted) element.        */
  71. /*----------------------------------------------------------------------*/
  72. unsigned low, high;
  73. {
  74.     (*gexch)(low, (low+high)/2);    /* partition on middle element    */
  75.     do
  76.     {    while (low < high AND (*gcomp)(low, high) <= 0)
  77.             high--;    /* find unsorted higher element    */
  78.         if (high ISNT low)
  79.         {    (*gexch)(low, high);
  80.             while (low < high AND (*gcomp)(low, high) <= 0)
  81.                 low++;    /* find unsorted lower element    */
  82.             if(low ISNT high)
  83.                 (*gexch)(low, high);
  84.         }
  85.     } while(low ISNT high);
  86.     return low;
  87. }
  88.